/**
 * @author: li_jian
 * @version: 1.0
 * @date: 2020/7/7 01:13
 * @description： @link{https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&&tqId=11160&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking}
 */
public class JZ7_斐波那契数列 {

    public int Fibonacci(int n) {
        return forCyclePro(n);
    }

    /**
     * 使用for循环实现，同时缓存前两个值
     * @param n
     * @return
     */
    private int forCyclePro(int n) {
        if (n <= 1)
            return n;
        int pre2 = 0, pre1 = 1;
        int fbi = 0;
        for (int i = 2; i <= n; i++) {
            fbi = pre1 + pre2;
            pre2 = pre1;
            pre1 = fbi;
        }

        return fbi;
    }

    /**
     * for循环实现
     *
     * @param n
     * @return
     */
    private int forCycle(int n) {
        if (n <= 1)
            return n;
        int[] fib = new int[n + 1];
        fib[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[n];
    }

    /**
     * 递归实现
     *
     * @param n
     * @return
     */
    private int recursion(int n) {
        if (n <= 1) return n;
        if (n <= 2) {
            return 1;
        }

        return recursion(n - 1) + recursion(n - 2);
    }

}
